#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class LRUCache
{
public:
    LRUCache(int capacity)
    {
        _capacity = capacity;
    }

    //获取数据.
    int get(int key)
    {
        //找到数据key的值.
        auto hashit = _hashmap.find(key);
        if(hashit != _hashmap.end())
        {
            //找到对应关键词
            auto listit = hashit->second;
            pair<int, int> kv = *listit;

            //删除原来对应关键词数据;
            _list.erase(listit);
            //现在头插关键词数据.
            _list.push_front(kv);
            //然后改变一下hashmap的key的值..
            _hashmap[key] = _list.begin();
            return kv.second;
        }
        else
        {
            return -1;
        }
    }

    //插入新的数据.key,value类型的.
    void put(int key, int value)
    {
        auto hashit = _hashmap.find(key);
        if(hashit == _hashmap.end())
        {
            //找不到对应的数据;
            if(_list.size() >= _capacity)
            {
                //大于容量.
                _hashmap.erase(_list.back().first);
                //删除最后一个数据.(这个数据很久没访问过的);
                _list.pop_back();
            }

            _list.push_front(make_pair(key, value));
            _hashmap[key] = _list.begin();
        }
        else
        {
            auto listit = hashit->second;
            pair<int, int> kv = *listit;
            kv.second = value;

            _list.erase(listit);
            _list.push_front(kv);
            _hashmap[key] = _list.begin();
        }
    }

private:
    //链表保存各个cache里的数据.
    list<pair<int, int>> _list;
    size_t _capacity;
    //使用下标和cache数据指针进行映射.
    unordered_map<int, list<pair<int, int>>::iterator> _hashmap;
};